#include <stdio.h>
#include "single_linked_list.cpp"

// 删除所有不带头节点的单链表L中所有值为x的节点
// 递归
void DeleteNode(LinkedList &L,int x) {
    LNode *ptr;
    if (L == NULL) 
        return;
    if (L->data == x) {
        ptr = L;
        L = L->next;
        free(ptr);
        DeleteNode(L,x);
    } else 
        DeleteNode(L->next,x);
}

// 非递归
void DeleteNode2(LinkedList &L, int x) {
    // 找到第一个不为x 的节点
    while (L != NULL){
        if (L->data == x){
            LNode *q = L;
            L = L->next;
            free(L);
        }
        else
            break;
    }   
    // 删除之后为x的节点
    LNode *ptr = L;
    while (ptr->next != NULL){
        if (ptr->next->data == x) {
            ptr->next = ptr->next->next;
        } 
        else 
            ptr = ptr->next;
    }
}

int main() {
    LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 2);
    ListAppend(L, 5);
    ListAppend(L, 9);
    ListAppend(L, 7);
    ListAppend(L, 3);
    ListAppend(L, 6);
    PrintList(L);

    // L 为带头节点的链表
    // L->next为第一个节点 即一个不带头结点的链表
    DeleteNode(L->next,7);
    PrintList(L);
    DeleteNode2(L->next,6);
    PrintList(L);

    return 0;
}